Recently, in information-processing technology, especially in the fields of image compression and image recognition, associative memories provided with minimum distance search capabilities have been attracting attention. The associative memories are very useful for pattern matching for object recognition needed in intelligent information processing, and the data compression using a data group called a code book.
The associative memory is a typical functional memory which has a function to search multiple items of reference data in the associative memory for a data item which best matches (is nearest to) an inputted data string (search data). Because of its excellent search capabilities, the associative memory is expected to dramatically improve performance of applications which have pattern matching capabilities for image compression and image recognition described above.
It is a basic process of pattern matching to find a data item closest to input data from R items of reference data each of which has a bit width of W (D. R. Tveter, “The Pattern Recognition Basis Of Artificial Intelligence,” Los Alamitos, Calif.: IEEE computer society, 1998). Thus, the minimum distance search associative memory plays a central role in information processing such as image compression and image recognition (Japanese Patent Laid-Open No. 2002-288985).
Existing fully-parallel minimum distance search associative memories which have been proposed include those which have search capabilities for one of the Hamming, Manhattan, and Euclidean distances which are simple distances. The distances are defined by Expression 1 and Expression 2 (H. J. Mattausch, T. Gyohten, Y. Soda, and T. Koide, “Compact Associative-Memory Architecture with Fully-Parallel Search Capability for the Minimum Hamming Distance”, IEEE Journal of Solid-State Circuits, Vol. 37, pp. 218-227, 2002).
                    [                  Expression          ⁢                                          ⁢          1                ]                                                            D        =                              ∑                          i              =              1                        w                    ⁢                                                                S                i                            -                              R                i                                                                                    Hamming        ⁢                                  ⁢        or        ⁢                                  ⁢        Manhattan        ⁢                                  ⁢        distance                                [                  Expression          ⁢                                          ⁢          2                ]                                                            D        =                                            ∑                              i                =                1                            w                        ⁢                                          (                                                      S                    i                                    -                                      R                    i                                                  )                            2                                                          Euclidean        ⁢                                  ⁢        distance            
where S={S1, S2, . . . , Sw} represents input data and R={R1, R2, . . . , RW} represents reference data. In Expression 1, when Si and Ri are 1-bit binary numbers, D is the Hamming distance, and when Si and Ri are n-bit binary numbers (n>1), D is the Manhattan distance. In Expression 2, D represents the Euclidean distance.
So far, there have been proposed a fully-parallel minimum Hamming distance search architecture (H. J. Mattausch, T. Gyohten, Y. Soda, and T. Koide, “Compact Associative-Memory Architecture with Fully-Parallel Search Capability for the Minimum Hamming Distance”, IEEE Journal of Solid-State Circuits, Vol. 37, pp. 218-227, 2002) and a fully-parallel minimum Manhattan distance search architecture (H. J. Mattausch, N. Omori, S. Fukae, T. Koide and T. Gyohten, “Fully-Parallel Pattern-Matching Engine with Dynamic Adaptability to Hamming or Manhattan Distance,” 2002 Symposium on VLSI Circuits Digest of Technical Papers, pp. 252-255, 2002; and Japanese Patent Laid-Open No. 2005-209317).
The associative memory includes a unit data storage circuit (US), unit data comparator circuit (UC), word comparator circuit (WC), winner line-up amplifier (WLA) circuit, and winner take all (WTA) circuit.
The unit data storage circuit stores reference data. The unit data comparator circuit (UC) compares the reference data with search data. The word comparator circuit converts a comparison signal into a current value. The winner line-up amplifier circuit (WLA circuit) converts a comparison current signal into a voltage and amplifies the resulting voltage. The winner take all circuit further amplifies an output from the WLA circuit. The associative memory also includes a search data storage circuit, row decoder, column decoder, and read/write circuit as peripheral circuits.
The unit data comparator circuit UC compares the reference data with the search data and the word comparator circuit WC outputs a comparison current signal C which represents results of comparison between the reference data and search data to the WLA circuit. The WLA circuit 100 converts the comparison current signal C into a comparison voltage signal LA and amplifies the resulting comparison voltage signal LA. The WTA circuit 200 further amplifies the comparison voltage signal LA. Eventually, the WTA circuit sets a threshold, and thereby outputs the best matching data (winner) as 1, and the other data (loser) as 0.